1. Field of the Invention
The present invention relates to a data compression method and an apparatus therefor.
2. Related Background Art
These years, images created on a computer under DTP have been required to have a high quality, and multicoloring and multigradating have been progressed. The volume of data for an image of such a kind, becomes large, that is, for example, about 4M bytes are required for an image on three-color printing having 400 dpi with 256 gradation. If image data are handled as code data such as Page Description Language, the volume of data can be less, but there has been raised such problems that a long time is required for decoding code data into image data and that original code data cannot be reproduced from an developed image.
As a data compression method for a multivalued color image in general, JPEG (Joint Photographic Expert Group) has recommended using a compression method of an ADCT (Adaptive Discrete Cosine Transform) type. Explanation will be made of this ADCT compression method.
Referring to FIG. 13 which is a block diagram showing a functional arrangement of an ADCT compression apparatus, a color space converting part 3101 converts a color space (NTSC-RGB) exhibited by color signals (red (R), green (G) and blue (B)) in an NTSC system, into a color space (YCrCb) exhibited by a luminance signal Y and two color-difference signals Cr, Cb. A subsampling part 3102 reduces color-difference data with the use of such a characteristic that the human eyes are sensitive to brightness but are not sensitive to color difference. Specifically, the subsampling part 3102 obtains an averaged value of two adjacent color-difference data so as to reduce the volume of color data into a one-half. A DCT (Discrete Cosine Transform) converting part 3103 divides image data received through from the sampling part 1302, into blocks which are vertically and horizontally adjacent to one other in an 8.times.8 array, and them subjects the same to DCT conversion so as to convert the image data into a frequency space. A quantization part 3104 divides 64 DCT coefficients by quantized values having different step widths. A Huffman encoding part 3105 separates the thus quantized 64 DCT coefficients between one and 63, and then codes the respective coefficients with the use of a Huffman table recommended by the JPEG. The thus encoded data are affixed with a header such as quantized table data or Huffman table date, and are stored in a memory or transmitted to another device or the like.
Referring to FIG. 14 which is a block diagram illustrating the functional configuration of an ADCT expansion unit, a Huffman decoding part 3205 decodes inputted coded data so as to produce quantized data. An inverse quantization part 3204 converts the quantized data produced in the Huffman coding part 3205 into CDT coefficient data. That is, the coefficient data can be obtained by multiplying 64 coefficients quantized values with quantized values by use of quantizing table data used during the quantization in the quantization part 3104. A reverse DCT conversion part 3203 converts the DCT coefficient data obtained in the reverse quantization part 3204 into actual image data. An interpolation part 3202 interpolates data Cr and Cb which have been absent by the sampling part 3102 during data compression, by simply using the so-called iteration process. A color space converting part 3201 converts YCrCb data into NTSC-RGB data or color space data for the device thereof.
Next, explanation will be made of the flow of the operation of the above-mentioned data compression apparatus and the expansion unit by exhibiting actual data.
FIG. 15 shows a part of image data or a multivalued color image created by a computer. That is, the data shown in FIG. 15 are NTSC-RGB data which are a part (16.times.16 pixels) of an image data developed from a character part of the multivalued color image. There are shown red (R) data 3301, green (G) data 3302 and blue (B) data 3303. Data of each of the pixels has a range of 8 bits (0 to 255). Further, this part is a part of an image in which a blue color character indicated by (R, G, B)=(30, 30, 225) is written on a base indicated by (R, G, B)=(225, 225, 225) which is more or less dark.
The conversion from NTSC-RGB into YCrCb, executed by the color space conversion part 3101, is made by the following expressions.
Y=0.299.times.R+0.587.times.G+0.114.times.B PA1 Cr=0.713 (R-Y) PA1 Cb=0.564 (B-Y) PA1 Y=219.0.times.Y+16.5 PA1 Cr=224.0.times.Cr+128.5 PA1 Cb=224.0.times.Cb+128.5 PA1 input means for serially inputting multi-level data; PA1 means for detecting a differential value between two consecutively inputted multi-level data; PA1 first detecting means for determining whether a first differential value detected by said detecting means is zero or not; PA1 first memory means for storing therein a value based upon the first differential value when the first differential value is not zero; PA1 second determining means for determining whether a second differential value detected by the detecting means coincides with the value stored in the first memory means, and PA1 output means for outputting encoded multi-level data in accordance with a result of the determination by the first and second determining means. PA1 pixel input means for inputting pixel data di! one pixel by one pixel, PA1 subtracting means for calculating a differential value diff between a present pixel di! and a one-before pixel di-1!; PA1 determining means for determining whether the differential value diff is zero or not; PA1 a number m of holding means for holding vectors vectn! (n=0 to m) having high occurability; PA1 a number m of comparing means for comparing the vectors vectn! with the differential value diff; PA1 computing means for computing the vectors vectn!; PA1 code output means for determining a compression code in accordance with results given by the determining means and the comparing means, and for outputting the compression code.
Further, by the recommendation of CCIR, the data are subjected to the following round-off (rounding) process in order to allow overshoot or undershoot during computation in the YCrCb color space.
YCrCb data obtained from the above-mentioned expressions are sampled for color difference data Cr, Cb in the sampling part 3102. As such a sampling process, a simple thinning process, a MAX data selecting process, a MIN data selecting process or the like can be used. However, an averaged value process will be used in this case. That is, an averaged value of data for two sequential pixels is taken so as to compress the data into a single one. In FIG. 16 which shows data having been obtained through the above-mentioned color space conversion part 3101 and the sampling part 3102, there are shown Y data (brightness data) 3401, Cr data (color difference data) 3402, and Cb data (color difference data) 3403. It is understood that each data Cr, Cb are reduced to one-half by the processing of the sampling part 3102.
Next, as shown in FIG. 16, Y data 3401, Cr data 3402 and Cb data 3403 are inputted into the DCT converting part 3103 where data are divided into blocks each having 8.times.8 data which are horizontally and vertically adjacent to one another. As the result of the division into the blocks, the Y data 3401 is divided into four blocks 3401a to 3401d. Similarly, the Cr data 3402 is divided into two blocks 3402a and 3402b. Similarly, the Cb data 3403 is divided into two blocks 3403a and 3403b. Further, these eight blocks are subjected to DCT conversion.
Referring to FIG. 17 which shows the result of the DCT conversion of the eight blocks shown in FIG. 8. Blocks 3501a to 3501d correspond respectively to four blocks 3401a to 3401d. Similarly, a block 3503 exhibits data obtained after the DCT conversion of the Cb data 3403. 64 coefficients of the blocks after the DCT conversion, consist of on DC component (left upper corner) and 63 AC components.
Next, the data 3501 to 3503 after the DCT conversion shown in FIG. 17 are quantized in the quantization part 3104.
A quantizing table recommended by JPEG is used as a quantizing table for the quantization carried out in this example. Referring to FIG. 22 which show the quantizing table, there are shown a table 4001 for Y components, a table 4002 for Cr components and Cb components. Data after the quantization process are shown in FIG. 18 in which there are shown post-quantization data 3601 of the Y data, post-quantization data 3602 of the Cr data and post-quantization data of the Cb data.
The respective post-quantization data 3601 to 3603 are separated into DC components and AC components in the Huffman coding part 3105. The DC components are used to obtain a histogram with respect to DC components in the previous blocks so as to create an optimum Huffman encoding table with which the encoding are carried out. The AC components are rearranged in a zig-zagging order as shown in FIG. 23. Further, for the AC components, a histogram is taken in the combination of run lengths of 0 (zero) during which a value X which is not zero is set in, and the values X so as to create an optimum Huffman table with which the encoding is carried out.
At this time, the data of 16.times.16 pixels in this NTSC-RGB has 795 bits. Since one pixels has 8 bits in the original image, it is resulted in 16.times.16.times.3 colors=786 bytes=6144 bits. That is, 1/7.7 of compression is made. Actually, this coded data is appended with an image size, a quantizing table, an encoding table and the like, and are stored in memory or are transmitted.
Explanation will be made of a process during expansion of data.
The image data processed by the ADCT compression process are inputted into the Huffman decoding part 3205 so as to be decoded. The inverse quantization part 3204 multiplies the data having being decoded in the Huffman decoding part 3205, with coefficients in the quantizing table shown in FIG. 22, that is, an inverse quantization process is carried out. From the above-mentioned process, data shown in FIG. 19 are obtained, that is, the data shown in FIG. 19 is obtained by carrying out the Huffman decoding process and the inverse quantization process for the data obtained by the above-mentioned ADCT compression process. It is clear that the data shown in FIG. 19 is different from the data before the compression shown in FIG. 17 in comparison therebetween.
The data shown in FIG. 19 is converted into YCrCb data in the inverse DCT conversion part 3202. FIG. 20 shows the YCrCb data. The data shown in FIG. 20 is converted into NTSC-RGB data in the color space conversion part 3201. FIG. 21 shows data which is finally obtained by the data expansion process.
As mentioned above, the above-mentioned ADCT compression process is an irreversible compression process accompanied with a loss of data during quantization. It is clear in comparison of FIG. 15 showing the NTSC-RGB data after the compression process, with the NTSC-RGB data shown in FIG. 21 which are resulted from the execution of the compression and expansion process for the data shown in FIG. 15. Thus, it is found that the image quality deteriorates.
An image created on a computer (a computer created image), such as DTP (desk top publishing) data, has advantages in that the outline is clear, and no-noise color-painting with a unicolor for a single pattern (or a character) can be made. However, if image data is processed by the ADCT compression process, disorder in the outline of a pattern, pseudo-edge (so-called mosquito noise), discoloration caused by quantization or the like occur, and accordingly, the advantages obtained by the computer created image cannot be demonstrated. In particular, since the above-mentioned compression process is a 8.times.8 block process, the color greatly varies in the boundary zone. If the compression rate is increased, the AC components are finally lost, resulting in occurrence of block distortion, and accordingly, an image having a resolution decreased to 1/8 is obtained.
Accordingly, although a compression process in which the compression is made by restraining the quantization to a degree at which the deterioration of the image is invisible, may be used, but it is not practicable in the compression rate since the computer created image originally has a feature that it has a large volume of high frequency data. Accordingly, it is required for a computer created image obtained by the DTP that the compression is made by a compression process in which a reversible high compression rate can be obtained.
Meanwhile, as to the reversible compression process, a run length compression process in which the length in which the same data are successive, is compressed may be used. For example, in a run length compression process for multivalued image data, a Huffman code which indicates that how many numbers of the same pixels succeed is appended with the pixel data thereof, next thereto. Such a compression can attain a relatively large compression rate as shown in FIG. 26B by appending data A after a Huffman code indicating 13, and data B after a Huffman code indicating 5, and data C to a Huffman code indicating 8 when a classical computer created image is processed as shown in FIG. 26B.
However, in the case of an image shown in FIG. 26C in which data successively change, since a Huffman code indicating 1 is appended thereafter with data A, a Huffman code indicating 1 thereafter with data B, a Huffman code indicating 1 thereafter with data C . . . , the data size become larger than that of "ABC . . . " which are, as a result, the same as original image data, and accordingly, the data sometime expand, rather than data compression.